#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 148. 排序链表.py
@time: 2022/1/15 15:04
@desc: https://leetcode-cn.com/problems/sort-list/
> 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

@解题思路：
    归并：
        1. 每次找到中间节点
        2. 递归归并左右区间
        3. 当分治到head的next是tail的时候，说明可以断链了，因此断开，此时递归到底了，可以合并了
        4. Ot(nlogn), Os(logn)
'''


# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):

    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        def merge(l1, l2):
            if not l1 and not l2: return None
            if l1 and not l2: return l1
            if not l1 and l2: return l2
            dummy = ListNode(-1)
            p = dummy
            while l1 and l2:
                if l1.val < l2.val:
                    p.next = l1
                    l1 = l1.next
                else:
                    p.next = l2
                    l2 = l2.next
                p = p.next
            if l1: p.next = l1
            if l2: p.next = l2
            return dummy.next

        def sort(head, tail):
            if not head: return None
            # 当前链表只有一个节点
            if head.next==tail:
                # 断链
                head.next = None
                return head
            slow, fast = head, head
            while not fast == tail:
                fast = fast.next
                slow = slow.next
                if not fast == tail:
                    fast = fast.next
            mid = slow
            return merge(sort(head, mid), sort(mid, tail))

        return sort(head, None)

if __name__ == '__main__':
    head = ListNode(4, next=ListNode(2, next=ListNode(1, next=ListNode(3))))
    res = Solution().sortList(head)
    print(res)